package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MergeIntervals {

	private class Interval {
		int start;
		int end;
		Interval() {
			start = 0;
			end = 0;
		}
		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}
	
	public List<Interval> merge(List<Interval> intervals) {
		int length = intervals.size();
		if(length <= 1){
			return intervals;
		}
        //思路：通过比较start对list进行排序，然后若前一个的end大于后面的start，那么就进行合并
        Collections.sort(intervals, new Comparator<Interval>() {
        	public int compare(Interval o1, Interval o2) {
        		return o1.start - o2.start;
        	};
		});
        List<Interval> list = new ArrayList<>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 0; i < length; i++) {
			if(end >= intervals.get(i).start){
				end = Math.max(end, intervals.get(i).end);
			}else{
			    list.add(new Interval(start, end));
			    start = intervals.get(i).start;
			    end = intervals.get(i).end;
			}
		}
        list.add(new Interval(start, end));
        return list;
    }
	
	
	//Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
	public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(intervals == null || intervals.size() <= 0){
        	return new ArrayList<Interval>();
        }
        intervals.add(newInterval);
        return merge(intervals);
    }
}
